//
// Description: 637. 二叉树的层平均值
// Created by Loading on 2025/7/2.
//

#include <bits/stdc++.h>
#include "Utils.h"

using namespace std;

vector<double> averageOfLevels(TreeNode *root) {
    vector<double> res;

    queue<TreeNode *> q;
    q.emplace(root);
    while (!q.empty()) {
        double sum = 0;
        int n = q.size();
        for (int i = 0; i < n; ++i) {
            auto node = q.front();
            sum += node->val;
            q.pop();

            if (node->left) {
                q.emplace(node->left);
            }
            if (node->right) {
                q.emplace(node->right);
            }
        }
        res.push_back(sum / n);
    }

    return res;
}

int main() {
    auto root = generateTreeNode({3, 9, 20, -1, -1, 15, 7});
    auto res = averageOfLevels(root);

    for (auto &x : res) {
        cout << x << ' ';
    }
    cout << endl;

    return 0;
}